import java.util.Arrays;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-08-25
 * Time: 22:40
 */
public class Solution {
    /**
     * 方法一: 排序, 中间位置就是占多数的
     */
    public int majorityElement1(int[] nums) {
        Arrays.sort(nums);
        int len = nums.length;
        int mid = (len / 2);
        return nums[mid];
    }

    /**
     * 方法二: 士兵对战, 只要不认识就同时杀死, 最后剩下的就是占多数的
     */
    public int majorityElement2(int[] nums) {
        int num = nums[0];
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (count == 0) {
                // 两败俱伤了
                num = nums[i];
                count = 1;
            } else {
                if (num == nums[i]) {
                    // 遇见自己人了
                    count++;
                } else {
                    // 遇见敌人了
                    count--;
                }
            }
        }
        return num;
    }

    /**
     *  方法三: 分治
     *  一个数占多数,那么将这个区间分成多个区间, 那么这个数必定在至少其中一个区间中还占多数
     *  这样将一个区间分成两个区间, 如果两个区间中的众数相同, 那么就是本区间的众数
     *  如果不相同, 那么就比较哪个更多, 较多的是众数
     */


    /**
     *  计算这个数的个数
     */
    public int getCount(int[] nums, int left, int right, int val) {
        int count = 0;
        for (int i = left; i <= right; i++) {
            if (nums[i] == val) {
                count++;
            }
        }
        return count;
    }

    public int getMajorityElement(int[] nums, int left, int right) {
        if (left == right) {
            return nums[left];
        }
        int mid = ((right - left) >> 1) + left;
        int l = getMajorityElement(nums, left, mid);
        int r = getMajorityElement(nums, mid + 1, right);
        if (l == r) {
            // 两段区间的众数相同, 那么就是答案
            return l;
        }
        int countL = getCount(nums, left, mid, l);
        int countR = getCount(nums, mid + 1, right, r);
        return countL > countR ? l : r;
    }


    public int majorityElement(int[] nums) {
        return getMajorityElement(nums, 0, nums.length - 1);
    }
}